package com.myc.subjects.hashmap;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * LeetCode题号：136
 *
 * 只出现一次的数字
 *
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 *
 * 说明：
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 *
 * 示例 1:
 * 输入: [2,2,1]
 * 输出: 1
 *
 * 示例2:
 * 输入: [4,1,2,1,2]
 * 输出: 4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/single-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Zhichuxianyicideshuzi {

    public static void main(String[] args) {
        int[] nums = new int[]{4,1,2,1,2};
        Zhichuxianyicideshuzi zhichuxianyicideshuzi = new Zhichuxianyicideshuzi();
        System.out.println(zhichuxianyicideshuzi.singleNumber4(nums));
    }

    /**
     * 方法一：暴力法
     * 时间复杂度：O(n^2)
     * 遍历数组每个元素为基准，再遍历该数组，找到与之相同的且下标不同的元素则为重复元素，反之则是唯一元素
     */
    public int singleNumber1(int[] nums) {
        for(int i = 0; i < nums.length; i++){

            boolean isDuplicate = false;//定义是否重复信号量

            for(int j = 0; j < nums.length; j++){

                if(nums[i] == nums[j] && i != j) isDuplicate = true;//找到第i个元素重复的第j个元素，则存在重复
                if(j == nums.length - 1 && !isDuplicate){//当j遍历到最后一个元素时信号量依然为false，则不存在重复元素，那么第i个元素就是结果
                    return nums[i];
                }
            }
        }
        return 0;//这里不会走到，但是必须要写。。。
    }

    /**
     * 方法二：利用HashMap（经典时间降维策略）
     * 时间复杂度：O(n)
     * 利用两数之和那道题总结的 经典时间降维策略：利用Map的containsKey方法使得时间复杂度降一个维度
     */
    public int singleNumber2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])) map.remove(nums[i]);//如果存在则删掉
            else map.put(nums[i], i);//不存在则加入，元素作为键，值其实不重要
        }
        return map.keySet().iterator().next();
    }

    /**
     * 方法三：利用HashSet（数学方法）
     * 时间复杂度：O(n)
     * 利用数学方法，遍历数组将其加入HashSet，对set中元素求和，和的两倍再减去原数组的数据求和，就得到了结果数据。
     */
    public int singleNumber3(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int arraySum = 0;//定义数组求和
        int setSum = 0;//定义set求和
        for(int i = 0; i < nums.length; i++){
            arraySum += nums[i];
            if(!set.contains(nums[i])) {//set中没有的话，累加求和同时元素加入set结合
                setSum += nums[i];
                set.add(nums[i]);
            }
        }
        return setSum * 2 - arraySum;//结果为set求和的两倍减去数组求和
    }

    /**
     * 方法四：数学方法（使用异或）
     * 时间复杂度：O(n)
     * java中的异或运算有以下的特点：
     * 1. a ^ a = 0  a ^ 0 = a
     * 2. 异或具有交换律和结合律
     * 这一题可以利用异或具有交换律的特点，我们将数组的所有元素逐个进行异或计算，得到最终的结果就是唯一的那个元素
     */
    public int singleNumber4(int[] nums) {
        int result = 0;
        for(int i = 0; i < nums.length; i++){
            result ^= nums[i];
        }
        return result;
    }

    //官方题解
    public int singleNumberOfficial(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

}

/**
 * 总结：
 * 1.经典将为策略的经典应用（利用HashMap的containsKey方法降低时间复杂度）
 * 2.多观察数组的特点善于利用数学解决问题
 * 3.善于利用java的特殊运算符解决问题
 */
